Typical DP Contest A - コンテスト
提出
TLE
code: python
import itertools
n = int(input())
p = list(map(int, input().split()))
ans = set()
for i in itertools.product(0, 1, repeat=len(p)): res = 0
for idx, j in enumerate(i):
if j:
ans.add(res)
print(len(ans))
WA
code: python
n = int(input())
p = list(map(int, input().split()))
for i in p:
# それぞれ一個ずつしか使えない
# for i in p:
# for j in range(10**5):
# if dpj and i + j < 10**5: 解答
code: python
n = int(input())
p = list(map(int, input().split()))
# p は順番に走査して問題ない
for v in p:
for i in range(10001 - v, -1, -1): # 今回加算した分が影響しないように上から見ていく
# print(dp)
# [1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0,
print(sum(dp))
テーマ
メモ